package day230425;

import java.util.Scanner;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/4/25 10:48
 * 斐波那契凤尾
 */
public class Main02 {

    public static void main(String[] args) {
        // 先计算前 10 0000 个斐波那契数
        long[] fibonacci = new long[100000];
        fibonacci[0] = 1;
        fibonacci[1] = 2;
        int border = -1; // 记录得数大于6位的边界, 用于控制输出格式
        for (int i = 2; i < fibonacci.length; i++) {
            long num = fibonacci[i-1] + fibonacci[i-2];
            if (border == -1 && num >= 1000000) {
                border = i + 1; // 从第 border 个斐波那契开始需要保留6位
            }
            fibonacci[i] = num % 1000000;
        }
        // 计算
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextInt()) {
            int n = scan.nextInt();
            if (n < border) {
                System.out.println(fibonacci[n-1]);
            } else {
                System.out.println(String.format("%06d", fibonacci[n-1]));
            }
        }
        scan.close();
    }
}
